Ana içeriğe geç

Sıralama Algoritmaları

Sıralama algoritmaları, bir veri kümesindeki öğeleri belirli bir sıraya göre düzenlemek için kullanılan matematiksel işlemlerdir. Sıralama algoritmaları, programlama ve veri yapıları gibi birçok bilgisayar bilimleri disiplininde yaygın olarak kullanılır. Aşağıda, en yaygın sıralama algoritmalarının birkaç örneği yer almaktadır:

  1. Bubble Sort: Her adımda bitişik öğeler karşılaştırılır ve gerektiğinde yer değiştirilir.
  2. Insertion Sort: İlk elemanı başlangıç olarak alarak, sonraki her elemanı doğru konuma yerleştirmek için önceki elemanlarla karşılaştırılır.
  3. Selection Sort: En küçük öğeyi bulup ilk öğeyle yer değiştirir, ardından ikinci küçük öğeyi bulup ikinci öğeyle yer değiştirir ve böyle devam eder.
  4. Merge Sort: Diziyi ortadan ikiye böler ve alt dizileri sıralar, ardından alt dizileri birleştirir.
  5. Quick Sort: Pivot olarak seçilen öğe sayesinde diziyi iki parçaya böler, daha sonra her parçayı ayrı ayrı sıralar.
  6. Heap Sort: Öğeler, max heap veya min heap gibi bir yapıya yerleştirilir ve sonra sıralanır.
  7. Counting Sort: Sayıların sayımı yapılır ve ardından dizideki öğeler, sıralama ölçütüne göre doğru konumlara yerleştirilir.
  8. Radix Sort: Sayıları belirli bir basamak değerine göre gruplandırarak sıralama işlemini gerçekleştirir.
  9. Shell Sort: İkili aralıklar kullanarak insertion sort benzeri bir yaklaşımla öğeleri sıralar.
  10. Cocktail Sort: Bubble sort'a benzer, fakat hem sağdan sola hem de soldan sağa geçiş yapar.
ipucu

Bu algoritmaların her birinin kendi avantajları ve dezavantajları vardır ve performansları veri kümesinin boyutuna, türüne ve sıralama ölçütüne bağlı olarak farklılık gösterir.

Bubble Sort​

Bubble Sort, bitişik öğeleri karşılaştırarak ve gerektiğinde yer değiştirerek bir diziyi sıralayan bir sıralama algoritmasıdır. Her adımda, en büyük öğe dizinin sonuna doğru yerleştirilir. Bu işlem, dizinin sıralı hale gelene kadar tekrarlanır.

Bubble Sort'un zaman karmaşıklığı O(n^2) dir, yani sıralanacak öğe sayısı arttıkça performansı dramatik olarak azalır.

İşleyiş örneği:

Dizimiz: [5, 2, 8, 3, 1, 9]

  1. İlk adımda, 5 ve 2 karşılaştırılır ve yer değiştirilir: [2, 5, 8, 3, 1, 9]
  2. Sonraki adımda, 5 ve 8 karşılaştırılır ve yer değiştirilmez: [2, 5, 8, 3, 1, 9]
  3. Sonraki adımda, 8 ve 3 karşılaştırılır ve yer değiştirilir: [2, 5, 3, 8, 1, 9]
  4. Sonraki adımda, 8 ve 1 karşılaştırılır ve yer değiştirilir: [2, 5, 3, 1, 8, 9]
  5. Sonraki adımda, 8 ve 9 karşılaştırılır ve yer değiştirilmez: [2, 5, 3, 1, 8, 9]
  6. İlk tur tamamlandıktan sonra en büyük öğe dizinin sonuna doğru yerleştirildi. Bu adımdan sonra, son öğe hariç tekrar tüm öğeler karşılaştırılacak.
    1. turda, 2 ve 5 karşılaştırılır ve yer değiştirilmez: [2, 5, 3, 1, 8, 9]
  8. 5 ve 3 karşılaştırılır ve yer değiştirilir: [2, 3, 5, 1, 8, 9]
  9. 5 ve 1 karşılaştırılır ve yer değiştirilir: [2, 3, 1, 5, 8, 9]
  10. 5 ve 8 karşılaştırılır ve yer değiştirilmez: [2, 3, 1, 5, 8, 9]
  11. İkinci tur tamamlandıktan sonra, sondan bir öğe hariç tüm öğeler karşılaştırılacak.

En son adımda [1, 2, 3, 5, 8, 9]'a ulaşılır.
— Sıralama Algoritmaları

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    printf("Dizinin orjinal hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    bubble_sort(arr, n);

    printf("\nDizinin Bubble Sort ile siralanmis hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Bu kod, verilen bir dizi üzerinde Bubble Sort'u uygular ve sıralanmış diziye karşılık gelen çıktıyı ekrana yazdırır.

Insertion Sort​

Insertion Sort, bir diziyi sıralamak için kullanılan bir algoritmadır. İşleyişi şu şekildedir:

  1. Dizi ilk eleman olarak kabul edilir ve zaten sıralanmış olarak düşünülür.
  2. Dizinin bir sonraki elemanı, sıralı bölgenin sonuna kadar (baştan başlayarak) karşılaştırılır ve doğru yerine yerleştirilir.
  3. Diğer elemanlar da bu şekilde sırayla karşılaştırılır ve doğru yerlerine yerleştirilir.

Insertion Sort, en iyi durumda (dizi zaten sıralı ise) O(n) karmaşıklığına sahiptir, ancak en kötü durumda (dizi ters sıralı ise) O(n^2) karmaşıklığına sahiptir.

İşte Insertion Sort algoritması için bir C kodu örneği:

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Sıralı bölgenin sonuna kadar key'i büyük olan elemanları yer değiştir */
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; /* key'i doğru yerine yerleştir */
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    printf("Dizinin orjinal hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    insertion_sort(arr, n);

    printf("\nDizinin Insertion Sort ile siralanmis hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Bu kod, verilen bir diziyi Insertion Sort kullanarak sıralar ve sıralanmış diziye karşılık gelen çıktıyı ekrana yazdırır.

Insertion Sort'ta Eleman Ekleme​

Insertion Sort algoritması kullanılarak bir eleman eklemek için örnek bir C kodu aşağıdaki şekildedir:

#include <stdio.h>

void insert(int arr[], int n, int key, int pos) {
    int i;
    for (i = n-1; i >= pos; i--) {
        arr[i+1] = arr[i];  // Elemanların sağa kaydırılması
    }
    arr[pos] = key;  // Yeni elemanın eklenmesi
}

void insertion_sort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Sıralı bölgenin sonuna kadar key'i büyük olan elemanları yer değiştir */
        while (j >= 0 && arr[j] > key) {
            j--;
        }
        insert(arr, i, key, j+1);  // key'in doğru yerine eklenmesi
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    printf("Dizinin orjinal hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    insert(arr, 6, 4, 2);  // Örnek olarak 4 elemanının 2. pozisyona eklenmesi

    printf("\nDizinin 4 elemanı eklendikten sonra hali: ");
    for (i = 0; i < n+1; i++)
        printf("%d ", arr[i]);

    insertion_sort(arr, n+1);

    printf("\nDizinin Insertion Sort ile siralanmis hali: ");
    for (i = 0; i < n+1; i++)
        printf("%d ", arr[i]);

    return 0;
}

Selection Sort​

Selection Sort, sıralanacak dizideki en küçük elemanı bulup, onu dizinin başına koyarak sıralama işlemini gerçekleştiren bir sıralama algoritmasıdır. Bu işlem sıralama tamamlanana kadar devam eder.

Örneğin, 5, 2, 8, 3, 1, 9 dizisi için Selection Sort işlemi şöyle gerçekleşir:

  • En küçük eleman 1 olduğu için 1 ile ilk eleman yer değiştirir.
  • En küçük eleman 2 olduğu için 2 ile ikinci eleman yer değiştirir.
  • En küçük eleman 3 olduğu için 3 ile üçüncü eleman yer değiştirir.
  • En küçük eleman 5 olduğu için 5 ile dördüncü eleman yer değiştirir.
  • En küçük eleman 8 olduğu için 8 ile beşinci eleman yer değiştirir.
  • En küçük eleman 9 olduğu için 9 ile altıncı eleman yer değiştirir.
  • Sıralama tamamlanır.

Selection Sort algoritmasının C kodu örneği şöyle:

#include <stdio.h>

void selection_sort(int arr[], int n) {
    int i, j, min_idx;

    // Her seferinde en küçük elemanı bulup, dizinin başına koyar
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    printf("Dizinin orjinal hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    selection_sort(arr, n);

    printf("\nDizinin Selection Sort ile siralanmis hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Bu kod, selection_sort() fonksiyonu kullanılarak diziyi sıralar. Fonksiyon, her seferinde en küçük elemanı bulup, dizinin başına koyarak sıralama işlemini gerçekleştirir.

Selection Sort'ta Ekleme​

Selection Sort algoritması, eleman ekleme işlemi için uygun bir yöntem değildir. Bu nedenle, eleman ekleme işlemi yapmak için her seferinde diziyi yeniden sıralamak gerekebilir.

Ancak, bazı durumlarda dizinin sonuna yeni bir eleman ekleneceği düşünülerek Selection Sort işlemi yapılır. Bu durumda, eklenecek eleman dizinin sonuna eklenir ve son elemanın yerine en küçük eleman konulur.

Örneğin, 5, 2, 8, 3, 1, 9 dizisi için Selection Sort işlemi ve sonrasında eleman ekleme işlemi şöyle gerçekleşir:

  • Selection Sort işlemi:

    • En küçük eleman 1 olduğu için 1 ile ilk eleman yer değiştirir.
    • En küçük eleman 2 olduğu için 2 ile ikinci eleman yer değiştirir.
    • En küçük eleman 3 olduğu için 3 ile üçüncü eleman yer değiştirir.
    • En küçük eleman 5 olduğu için 5 ile dördüncü eleman yer değiştirir.
    • En küçük eleman 8 olduğu için 8 ile beşinci eleman yer değiştirir.
    • En küçük eleman 9 olduğu için 9 ile altıncı eleman yer değiştirir.
    • Sıralama tamamlanır.

  • Eleman ekleme işlemi:

    • Dizinin sonuna 4 eklendi.
    • En küçük eleman 1 olduğu için 1 ile son eleman yer değiştirir.
    • En küçük eleman 2 olduğu için 2 ile son ikinci eleman yer değiştirir.
    • En küçük eleman 3 olduğu için 3 ile son üçüncü eleman yer değiştirir.
    • Sıralama tamamlanır ve dizinin son hali şöyle olur: 1, 2, 3, 4, 5, 8, 9.

Aşağıdaki C kodu, yukarıdaki örneği uygular ve sonuç dizisini ekrana yazdırır:

#include <stdio.h>

void selection_sort(int arr[], int n) {
    int i, j, min_idx;

    // Her seferinde en küçük elemanı bulup, dizinin başına koyar
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    printf("Dizinin orjinal hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    selection_sort(arr, n);

    printf("\nDizinin Selection Sort ile siralanmis hali: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Merge Sort​

Merge Sort, bir diziyi sıralamak için kullanılan bir sıralama algoritmasıdır. Divide-and-conquer (böl ve yönet) prensibine dayanır ve bir diziyi sıralamak için önce diziyi iki eşit parçaya bölerek her bir parçayı ayrı ayrı sıralar, daha sonra bu iki parçayı birleştirerek sıralı bir dizi elde eder.

Merge Sort algoritması, bir diziyi sıralamak için O(n log n) zaman karmaşıklığına sahiptir. Ancak, Merge Sort algoritması, veri dizisinin büyüklüğüne bağlı olarak daha fazla bellek kullanır.

Aşağıdaki C kodu, Merge Sort algoritmasını uygular:

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    // Geçici diziler oluşturulur
    int L[n1], R[n2];

    // Geçici dizilerin elemanları ana diziye kopyalanır
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    // İki geçici dizinin elemanları karşılaştırılır ve birleştirilir
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Geçici dizilerin kalan elemanları ana diziye kopyalanır
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        // Dizinin orta noktası hesaplanır
        int m = l+(r-l)/2;

        // İlk yarısı sıralanır
        merge_sort(arr, l, m);

        // İkinci yarısı sıralanır
        merge_sort(arr, m+1, r);

        // İki yarım birleştirilir
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    merge_sort(arr, 0, arr_size - 1);

    printf("Sıralanmış dizi: ");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    
    return 0;
}

Quick Sort​

Quick Sort, hızlı sıralama olarak bilinen, veri kümesini sıralamak için kullanılan bir sıralama algoritmasıdır. Divide and Conquer (böl ve yönet) algoritma tasarım yöntemine dayanmaktadır.

Algoritma, bir pivot eleman seçerek veri kümesini iki alt listeye ayırır, bir alt liste pivot elemanından küçük elemanları içerirken diğer alt liste ise pivot elemanından büyük elemanları içerir. Daha sonra her iki alt liste ayrı ayrı aynı işleme tabi tutulur ve bu işlem sıralı veri kümesini oluşturacak şekilde birleştirilir.

Aşağıda Quick Sort'un C kodu örneği verilmiştir:

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // pivot elemanını seç
    int i = low - 1; // küçük elemanlar için indeks
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) { // pivot elemanından küçük olanları bul
            i++; // küçük eleman indeksini artır
            swap(&arr[i], &arr[j]); // elemanları değiştir
        }
    }
    swap(&arr[i + 1], &arr[high]); // pivot elemanını doğru konuma taşı
    return (i + 1); // pivot elemanının yeni indeksini döndür
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high); // pivot elemanını bul
        quickSort(arr, low, pivot - 1); // pivot elemanından küçük olanları sırala
        quickSort(arr, pivot + 1, high); // pivot elemanından büyük olanları sırala
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sıralanmış dizi: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Heap Sort​

Heap Sort, öncelik kuyruğu yapısı kullanarak bir dizi içindeki elemanları sıralamak için kullanılan bir sıralama algoritmasıdır. Diziyi öncelik kuyruğuna dönüştürerek sıralama yapılır.

Algoritmanın çalışma mantığı şöyledir:

  1. Verilen diziyi bir Max Heap (en büyük öğenin kök olduğu bir ağaç) şeklinde düzenleyin.
  2. En büyük öğeyi alın ve son elemanla yer değiştirin.
  3. Yeni kök için Max Heap özelliğini sağlamak için dizinin kökünden aşağı doğru bir Heapify işlemi gerçekleştirin.
  4. Adımlar 2-3'ü dizinin tüm elemanları için tekrarlayın.

Heap Sort, en kötü durumda bile O(n log n) performansı sağlar.

İşte Heap Sort için C kodu örneği:

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Verilen alt ağaç için Heapify işlemi gerçekleştirir.
void heapify(int arr[], int n, int i) {
    int largest = i; // En büyük öğe kök olacak
    int left = 2 * i + 1; // Sol çocuk düğümü
    int right = 2 * i + 2; // Sağ çocuk düğümü

    // Sol çocuk kökten daha büyükse
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // Sağ çocuk kökten daha büyükse
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // Eğer en büyük eleman kök değilse
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        // Alt ağacı yeniden düzenlemek için recursive çağrı
        heapify(arr, n, largest);
    }
}

// Diziyi Heap olarak sıralama işlemi
void heapSort(int arr[], int n) {
    // Verilen diziyi Max Heap'a dönüştürün
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // En büyük elemanı sırayla dizinin sonundaki elemanlarla değiştirin
    for (int i = n - 1; i >= 0; i--) {
        // Kökü alın ve son elemanla yer değiştirin
        swap(&arr[0], &arr[i]);

        // Heapify işlemi çağrılır
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sıralanmış dizi: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Counting Sort​

Counting Sort, özellikle küçük sayılarla çalışırken hızlı bir sıralama algoritmasıdır. Diğer sıralama algoritmalarının aksine, karşılaştırma yapmaz ve sıralanacak elemanların sayılarını sayarak sıralar. Bu nedenle, verilerin sıralanacağı aralık önceden bilinmelidir.

Counting Sort, verilerin en küçük ve en büyük değerlerinin bilinmesi gereken bir sıralama algoritmasıdır. Veriler, öncelikle aralıklarına ayrılır ve daha sonra bu aralıkların sayıları sayılır. Daha sonra, her aralık, önceki aralıkla toplanarak yerlerine yerleştirilir.

#include <stdio.h>
#define RANGE 10 // 0'dan 9'a kadar olan sayılar

void countingSort(int arr[], int n) {
    int i, count[RANGE + 1] = {0};
    int output[n];

    // sayma işlemi
    for (i = 0; i < n; i++)
        count[arr[i]]++;

    // count[] dizisindeki elemanlar değiştiriliyor
    for (i = 1; i <= RANGE; i++)
        count[i] += count[i - 1];

    // output dizisine sıralama işlemi yapılıyor
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // output dizisi orijinal dizinin yerine kopyalanıyor
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 6, 8, 5, 3, 9, 1, 0, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, n);

    printf("Sıralanmış dizi: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Bu kod örneği, verilen dizi [4, 2, 6, 8, 5, 3, 9, 1, 0, 7] için Counting Sort algoritmasını uygular ve çıktı olarak sıralanmış diziyi verir.

Radix Sort​

Radix Sort, diğer sıralama algoritmalarından farklı olarak sayıları basamaklarına ayırarak sıralayan bir algoritmadır. En düşük basamaktan en yüksek basamağa doğru sıralama yapar. Basamak sayısı kadar geçici bir dizi oluşturulur ve her sıralama işlemi için sayılar bu geçici diziye aktarılır.

title: Radix Sort and Shell Sort in C description: This document provides an explanation and code examples for the Radix Sort and Shell Sort algorithms in C. It describes their working principles and implementation details.

keywords: [Radix Sort, Shell Sort, sorting algorithms, C programming, algorithm implementation]​

Radix Sort​

Bu kod örneği, verilen dizi [170, 45, 75, 90, 802, 24, 2, 66] için Radix Sort algoritmasını uygular ve çıktı olarak sıralanmış diziyi verir.

#include <stdio.h>

void countingSort(int arr[], int n, int exp) {
    int i, count[10] = {0};
    int output[n];

    // sayma işlemi
    for (i = 0; i < n; i++)
        count[(arr[i]/exp)%10]++;

    // count[] dizisindeki elemanlar değiştiriliyor
    for (i = 1; i < 10; i++)
        count[i] += count[i-1];

    // output dizisine sıralama işlemi yapılıyor
    for (i = n-1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10]-1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }

    // output dizisi orijinal dizinin yerine kopyalanıyor
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int i, exp;
    int max = arr[0];

    // En büyük sayıyı bulma işlemi
    for (i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // basamaklarına göre sıralama işlemi
    for (exp = 1; max/exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);

    radixSort(arr, n);

    printf("Sıralanmış dizi: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}
ipucu

Radix Sort, sayıları basamaklarına göre sıraladığı için, pozitif tam sayılar üzerinde en iyi performansını gösterir.

Shell Sort​

Shell Sort, Insertion Sort gibi bir sıralama algoritmasıdır ve temelinde Insertion Sort'u optimize etmek için tasarlanmıştır. Shell Sort, bir dizi elemanı küçük parçalara böler ve daha sonra bu küçük parçaları Insertion Sort ile sıralar.

Algoritma şu şekildedir:

  1. Dizi elemanlarını belirli bir aralıkla birbirinden ayırın.
  2. Ayırdığınız her parçayı Insertion Sort ile sıralayın.
  3. Parçaları tekrar birleştirin ve birleştirirken sıralı hale getirin.

Shell Sort, farklı aralıklarla elemanları ayırarak, daha hızlı bir sıralama yapmayı hedefler. Bu aralıklar genellikle dizi boyutunun yarısıdır ve her sıralama adımında yarıya düşürülür.

Shell Sort'un C kodu örneği aşağıdaki gibidir:

void shellSort(int arr[], int n) {
    // aralıkları belirle
    for (int gap = n/2; gap > 0; gap /= 2) {
        // parçalara ayır ve Insertion Sort'u uygula
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}
bilgi

Burada, gap değişkeni parçalar arasındaki mesafeyi belirler. İlk adımda gap değeri, dizinin yarısı olarak belirlenir. Daha sonra her adımda gap değeri yarıya düşürülür.

not

İkinci adımda, dizi elemanları gap değeri ile parçalara ayrılır ve her parça Insertion Sort ile sıralanır.

Son adımda, tüm parçalar birleştirilir ve sıralı hale getirilir.